package main.java.indi.zyj.coderecord;

import java.util.Stack;

public class LargestRectangleArea {



    public int largestRectangleArea(int[] heights) {
        int[] newHeight = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeight, 1, heights.length);
        newHeight[heights.length + 1] = 0;
        newHeight[0] = 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        int res = 0;
        for (int i = 1; i < newHeight.length; i++) {
            while (newHeight[i] < newHeight[stack.peek()]) {
                int mid = stack.pop();
                int w = i - stack.peek() - 1;
                int h = newHeight[mid];
                res = Math.max(res, w * h);
            }
            stack.push(i);

        }
        return res;
    }




    public int largestRectangleArea1(int[] heights) {

        int[] newHeights = new int[heights.length + 2];
        newHeights[0] = newHeights[newHeights.length - 1] = 0;
        for (int i = 0; i < heights.length; i++) {
            newHeights[i + 1] = heights[i];
        }
        heights = newHeights;

        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        int res = 0;

        for (int i = 1; i < heights.length; i++) {
            int topNum = heights[stack.peek()];
            if (topNum == heights[i]) {
                stack.pop();
                stack.push(i);
            } else if (heights[i] > topNum) {
                stack.push(i);
            } else {
                while (heights[i] < topNum) {
                    int right = i;
                    int mid = stack.peek();
                    stack.pop();
                    int left = stack.peek();
                    int h = heights[mid];
                    int w = right - left - 1;
                    res = Math.max(res, h * w);
                    topNum = heights[stack.peek()];
                }
                stack.push(i);
            }
        }
        return res;
    }

}
